#include <stdio.h>
#include <stdlib.h>           //malloc() 需要 stdlib.h 库
#include "../../include/type_list.h"

//初始化线性表
Status Initlist_Sq(Sqlist & L){
    //使用 malloc 动态分配一段内存，构造一个空的线性表      
    //malloc 函数：void * malloc(size_t  size);
    L.elem = (ElemType *) malloc (LIST_INIT_SIZE * sizeof (ElemType));
    if (! L.elem) exit (OVERFLOW);                      //存储分配失败 
    L.length = 0; //空表长度为 0 
    L.listsize= LIST_INIT_SIZE;                         //初始存储容量 
    return OK;
}// Initlist_Sq

//线性表的插入
Status ListInsert_Sq (Sqlist &L, int i, ElemType e){    //整个Sqlist &L，的 Sqlist & 表示 C++ 中的引用，所有可以直接 L.

    //在顺序线性表工中第 i 个位置（从 1 开始）之前插入新的元素 e, 
    //i 的合法值为 1 ≤ i ≤ ListLength_Sq (L) + 1，在第 ListLength_Sq (L) + 1 之前就是在整个线性表的最后
    if (i < 1 || i > L.length + 1) return ERROR;        // i 值不合法

    if (L.length >= L.listsize){                  
        //当前存储空间已满，增加分配
        //void *realloc(void * ptr, size_t  size); realloc()函数将旧空间释放掉并申请一个新空间，保证旧空间的数据会复制到新空间中，可以将小空间的数据放到大空间中，数据不会丢失但是不保证多出来的空间清零
        ElemType * newbase = (ElemType *) realloc (L.elem, (L.listsize + LISTINCREMENT) * sizeof (ElemType)); 
        if (! newbase) exit (OVERFLOW);                 //存储分配失败 
        L.elem = newbase;                               //新基址 
        L.listsize += LISTINCREMENT;                    //增加存储容量
    }

    //a[i] 的解释：a[i] = *(a + i)，而 L.elem 是分配的首地址，所以 L.elem[i - 1] = * (L.elem + i - 1)，即索引为 i - 1 的元素的值
    ElemType * q = & (L.elem[i - 1]);                               //q 为插入位置，因为 c 语言索引从 0 开始，索引第 i 个元素的索引为 i - 1

    //倒着往前循环，否则后边的元素会将前边的覆盖
    ElemType * p = 0;
    for(p = &(L.elem[L.length - 1]); p >= q; --p) 
        * (p + 1) = * p;                                //插入位置及之后的元素右移

    * q = e;                                            //插入 e
    ++ L.length;                                        //表长增 1

    return OK;

}// ListInsert_Sq

void Mergelist_Sq (Sqlist La, Sqlist Lb, Sqlist & Lc){

    //已知顺序线性表 Ia 和 b 的元素按值非递减排列
    //归并 Ia 和 b 得到新的顺序线性表 Ie, Ic 的元素也按值非递减排列
    ElemType * pa = La.elem; 
    ElemType * pb = Lb.elem;
    Lc.listsize = Lc.length = La.length + Lb.length;

    ElemType * pc = Lc.elem = (ElemType *) malloc (Lc.listsize * sizeof (ElemType));

    if (! Lc.elem) exit (OVERFLOW);                     //存储分配失败

    ElemType * pa_last = La.elem + La.length - 1;
    ElemType * pb_last = Lb.elem + Lb.length - 1;

    while (pa <= pa_last && pb <= pb_last) {            //归并
        if( * pa <= * pb) 
            * pc ++ = * pa ++;                          // 这里的 ++ 操作可认为是先执行了 * pc = * pa，然后 pc ++，pa ++
        else 
            * pc ++ = * pb ++;
    }
    while  (pa <= pa_last)  * pc ++ = * pa ++;           //插入 Ia 的剩余元素 
    while  (pb <= pb_last)  * pc ++ = * pb ++;           //插入h 的剩余元素 

}//Mergelist. Sq

//线性表的删除
Status ListDelete_Sq (Sqlist &L, int i, ElemType &e){

    //在顺序线性表 L 中刪除第 i 个元素，并用 e 返回其值 
    // i 的合法值为 1 ≤ i ≤ ListLength_Sq(L)
    if ((i < 1) || (i > L.length)) return ERROR;        //i 值不合法
    ElemType * p = & (L.elem[i - 1]);                   // p 为被删除元素的地址
    e = *p;                                             //被删除元素的值赋给 e
    ElemType * q = L.elem + L.length - 1;               //表尾元素的地址

    for (++p; p <= q; ++p)
        * (p - 1) = * p;                                //被删除元素之后的元素左移

    -- L.length;                                         //表长减 1 

    return OK;
}// ListDelete.Sq
